package com.lw.leetcode.back.b;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 面试题 04.01. 节点间通路
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/28 17:13
 */
public class FindWhetherExistsPath {

    public static void main(String[] args) {
        FindWhetherExistsPath test = new FindWhetherExistsPath();

        // true
//        int[][] arr = {{0, 1}, {0, 2}, {1, 2}, {1, 2}};
//        int st = 0;
//        int end = 2;
//        int n = 3;

        // true
//        int[][] arr = {{0, 1}, {0, 2}, {0, 4}, {0, 4}, {0, 1}, {1, 3}, {1, 4}, {1, 3}, {2, 3}, {3, 4}};
//        int st = 0;
//        int end = 4;
//        int n = 3;

        // false
        int[][] arr = {{0, 1}, {1, 2}, {1, 3}, {1, 10}, {1, 11}, {1, 4}, {2, 4},
                {2, 6}, {2, 9}, {2, 10}, {2, 4}, {2, 5}, {2, 10}, {3, 7}, {3, 7},
                {4, 5}, {4, 11}, {4, 11}, {4, 10}, {5, 7}, {5, 10}, {6, 8}, {7, 11}, {8, 10}};
        int st = 2;
        int end = 3;
        int n = 12;
        boolean whetherExistsPath = test.findWhetherExistsPath(n, arr, st, end);
        System.out.println(whetherExistsPath);
    }

    private HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
    private Set<Integer> set = new HashSet<>();
    private int target;

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        this.target = target;
        for (int i = 0; i < n; i++) {
            map.put(i, new HashSet<>());
        }
        for (int[] g : graph) {
            map.get(g[0]).add(g[1]);
        }
        return find(start, target);
    }

    private boolean find(int start, int target) {
        if (start == target) {
            return true;
        }
        if (set.contains(start)) {
            return false;
        }
        set.add(start);
        for (Integer neighbor : map.get(start)) {
            if (find(neighbor, target)) {
                return true;
            }
        }
        return false;
    }


//    private Map<Integer, Integer> map = new HashMap<>();
//    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
//        for (int[] ints : graph) {
//            int a = find(ints[0]);
//            int b = find(ints[1]);
//            if (a != b) {
//                map.put(b, a);
//            }
//        }
//        return find(start) == find(target);
//    }
//    private int find(int t) {
//        if (!map.containsKey(t)) {
//            return t;
//        }
//        int f = map.get(t);
//        int i = find(f);
//        if (f != i) {
//            map.put(f, i);
//        }
//        return i;
//    }

}
